package 算法.leetcode.offer;

/**
 * https://leetcode-cn.com/problems/chou-shu-lcof/solution/mian-shi-ti-49-chou-shu-dong-tai-gui-hua-qing-xi-t/
 * @author lchenglong
 * @date 2022/4/20
 */
public class Offer49 {

    public static void main(String[] args) {
        Offer49 instance = new Offer49();
        int ans = instance.nthUglyNumber(1352);
        System.out.println(ans);
    }

    /**
     * dp[a]×2>dp[i−1]≥dp[a−1]×2
     * dp[b]×3>dp[i−1]≥dp[b−1]×3
     * dp[c]×5>dp[i−1]≥dp[c−1]×5
     * @param n
     * @return
     */
    public int nthUglyNumber(int n) {
        int[] dp = new int[n];
        int a=0,b=0,c=0;
        // 第一个丑数
        dp[0] = 1;
        for (int i=1;i<n;i++){
            int n2 = dp[a]*2,n3 = dp[b]*3,n5 = dp[c] *5;
            dp[i] = Math.min(Math.min(n2,n3),n5);
            if (dp[i] == n2) a++;
            if (dp[i] == n3) b++;
            if (dp[i] == n5) c++;
        }
        return dp[n-1];
    }

}
